/**
 * @file 哈希
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-10
 * 
 * @copyright Copyright (c) 2021
 * 
 * 242.有效的字母异位词
 * 49.字母异位词分组
 * 439.找到字符串中所有的字母异位词
 * 383.赎金信
 * 349.两数组的交集
 * 350.两数组的交集II
 * 202.快乐数
 */
#include <cmath>
#include <unistd.h>

#include <algorithm>
#include <iostream>
#include <memory>
#include <numeric>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    class T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}
void printBool(bool b)
{
    if (b) {
        cout << "True" << endl;
    } else {
        cout << "False" << endl;
    }
}

class Solution
{
public:
    bool isAnagram(string s, string t)
    {
        if (s.length() != t.length()) {
            return false;
        }
        vector<int> cnt(26, 0);
        for (int i = 0; i < s.length(); ++i) {
            cnt[s[i] - 'a'] += 1;
            cnt[t[i] - 'a'] -= 1;
        }
        for (int i = 0; i < 26; ++i) {
            if (cnt[i] != 0) {
                return false;
            }
        }
        return true;
    }
    // 49.
    vector<vector<string>> groupAnagrams(vector<string> &strs)
    {
        // 计数法
        // 这题的难点是map里放什么
        // key:26个字母的数组 val:str
#if 0
        // 自定义对 array<int, 26> 类型的哈希函数
        auto arrayHash = [fn = hash<int>{}](const vector<int> &arr) -> size_t {
            return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
                return (acc << 1) ^ fn(num);
            });
        };

        unordered_map<vector<int>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
        for (string &str : strs) {
            vector<int> cnt(26, 0);
            for (char &ch : str) {
                cnt[ch - 'a'] += 1;
            }
            mp[cnt].emplace_back(str);
        }
        vector<vector<string>> res;
        for (auto it = mp.begin(); it != mp.end(); ++it){
            res.emplace_back(it->second);
        }
        return res;
#endif
        // 用string代替vector<int> 但是这样的话每个字符的存储上限是256
        // 还有种方法是用排序string作为key，那样不会有问题，就是复杂度高些
        unordered_map<string, vector<string>> mp;
        for (string &str : strs) {
            string cnt(26, 0);
            for (char &ch : str) {
                cnt[ch - 'a'] += 1;
            }
            mp[cnt].emplace_back(str);
        }
        vector<vector<string>> res;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            res.emplace_back(it->second);
        }
        return res;
    }
    // 438.
    vector<int> findAnagrams(string s, string p)
    {
        // 这不是滑窗吗，两数组可以精简成一个，注意谁++谁--就行
        vector<int> cntp(26, 0);
        vector<int> cntw(26, 0);
        vector<int> res;
        for (int i = 0; i < p.size(); ++i) {
            ++cntp[p[i] - 'a'];
            ++cntw[s[i] - 'a'];
        }
        if (isAnagrams(cntp, cntw)) {
            res.emplace_back(0);
        }
        for (int i = p.size(); i < s.size(); ++i) {
            ++cntw[s[i] - 'a'];
            --cntw[s[i - p.size()] - 'a'];
            if (isAnagrams(cntp, cntw)) {
                res.emplace_back(i);
            }
        }
        return res;
    }

private:
    bool isAnagrams(vector<int> &a, vector<int> &b)
    {
        for (int i = 0; i < 26; ++i) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }

public:
    // 383.
    bool canConstruct(string ransomNote, string magazine)
    {
        // 从杂志上剪字母组成ransomNote
        vector<int> cnt(26, 0);
        for (int i = 0; i < magazine.size(); ++i) {
            ++cnt[magazine[i] - 'a'];
        }
        for (int i = 0; i < ransomNote.size(); ++i) {
            int idx = ransomNote[i] - 'a';
            if (cnt[idx] == 0) {
                return false;
            }
            --cnt[idx];
        }
        return true;
    }
    // 202.
    bool isHappy(int n)
    {
        // 不是快乐数，就会无限循环，循环的本质是平方和相同
        // 打表，相同的数查询2次就算false
#if 0
        unordered_set<int> table;
        while (n != 1){
            n = getSum(n);
            auto it = table.find(n);
            if (it != table.end()){
                return false;
            }
            table.insert(n);
        }
        return true;
#endif
        // 快慢指针 wocao
        int slow = n, fast = getSum(n);
        // 若是快乐数，那也是快指针先到
        while (slow != fast && fast != 1) {
            slow = getSum(slow);
            fast = getSum(getSum(fast));
        }
        return fast == 1 ? true : false;
    }

private:
    int getSum(int n)
    {
        int sum = 0;
        while (n) {
            int a = n % 10;
            sum += a * a;
            n /= 10;
        }
        return sum;
    }

public:
    // 349.
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        // 计算交集，结果唯一
        unordered_set<int> st(nums1.begin(), nums1.end());
        unordered_set<int> res;
        for (int i = 0; i < nums2.size(); ++i) {
            auto it = st.find(nums2[i]);
            if (it != st.end()) {
                res.insert(nums2[i]);
            }
        }
        return vector<int>(res.begin(), res.end());
    }
    // 350.
    vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
    {
        // 结果有重复
#if 0
        unordered_map<int, int> mp;
        vector<int> res;
        for (int &num : nums1) {
            mp[num] += 1;
        }
        for (int &num : nums2) {
            auto it = mp.find(num);
            if (it != mp.end()) {
                if (it->second) {
                    res.push_back(num);
                    mp[num] -= 1;
                }
            }
        }
        return res;
#endif
        /*** 进阶三问：
         * 进阶 若已有序
         * 若一个数组很短小，将其hash，在另一个数组中根据hash表找，哈希更优
         * 如果内存十分小，不足以将全部数组载入内存，那就不能哈希了，只能排序双指针
         * ps.归并外排
         * **/
        
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());
        int i = 0, j = 0;
        int n = nums1.size(), m = nums2.size();
        vector<int> res;
        while (i < n && j < m) {
            if (nums1[i] == nums2[j]) {
                res.push_back(nums1[i]);
                ++i, ++j;
            } else if (nums1[i] < nums2[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        return res;
    }
};

Solution solve = Solution();

void test383()
{
    string a = "aaa", b = "aabb";
    printBool(solve.canConstruct(a, b));
}

void test202()
{
    int n = 469;
    printBool(solve.isHappy(n));
}

int main()
{
    // test383();
    test202();
    return 0;
}